package com.zklh.leetcode.chain;

/**
 * 用于判断传入链条是否是回文结构
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/4/12 14:31
 */
public class PalindromeChain {

    // 相对节点, 与当前头结点相对的节点
    public ListNode relativeListNode;

    public boolean isPalindrome(ListNode head){
        relativeListNode = head;
        return traverse(head);
    }

    public boolean isPalindrome2(ListNode head){
        if (head.next == null) {
            return true;
        }
        // 使用快慢指针实现
        ListNode slow=head,fast=head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        slow = reverse(slow);
        ListNode left = head;
        boolean result = true;
        while (slow != null) {
            result &= slow.val == left.val;
            slow = slow.next;
            left = left.next;
        }
        return result;

    }

    private ListNode reverse(ListNode head) {
        ListNode now = head;
        ListNode pre = null;
        ListNode tempListNode;
        ListNode newHead = head;
        while (now != null) {
            newHead = now;
            tempListNode = now.next;
            now.next = pre;
            pre = now;
            now = tempListNode;
        }
        return newHead;
    }

    // 遍历节点, 在遍历过程中, 比较是否和对应节点相等, 全部相等才会返回true
    public boolean traverse(ListNode head){
        if (head == null) {
            return true;
        }
        boolean result = traverse(head.next);
        result &= relativeListNode.val == head.val;
        relativeListNode = relativeListNode.next;
        return result;
    }

    public static class ListNode {
        int val;

        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next= new ListNode(2);
        head.next.next= new ListNode(2);
        head.next.next.next= new ListNode(1);

        PalindromeChain palindromeChain = new PalindromeChain();
        System.out.println(palindromeChain.isPalindrome2(head));

    }

}
